local depth_list = class("DepthList"){
    __root_node = {___is_root___ = true},
    __tail_node = nil,
    __all_node = {},
    __node_number = 0,
    __node_index = {},
    __interval = {},
    _interval_size = 200,
}

local function list_insert_node_back(self,onode)
    local tail = self.__tail_node
    tail.__next_node__ = onode
    onode.__up_node__ = tail
    onode.__next_node__ = nil
    self.__tail_node = onode
    self.__all_node[onode] = onode
    self.__node_number = self.__node_number + 1
    return onode
end

local function list_insert_self_up(self,node,inode)--向身前插入节点
    if node == inode then return end
    if not node or not inode then return end
    local up = node.__up_node__
    up.__next_node__ = inode
    inode.__up_node__ = up
    inode.__next_node__ = node
    node.__up_node__ = inode
    self.__all_node[inode] = inode
end

local function list_nswap(self,na,nb)--基于节点的交换
    if na == self.__root_node or nb == self.__root_node then return end

    local na_up = na.__up_node__
    local na_ne = na.__next_node__
    local nb_up = nb.__up_node__
    local nb_ne = nb.__next_node__

    if na_ne == nb then--相邻  	    A < - > na < - > nb < - > B
        nb.__up_node__      = na_up 		--  A < - - nb - - - na - - - b
		na_up.__next_node__ = nb     	--  A < - > nb - - - na - - - b
        nb.__next_node__    = na	   		--  A < - > nb - - > na - - - b
		na.__up_node__	  = nb	   		--  A < - > nb < - > na - - > b
        na.__next_node__    = nb_ne		--  A < - > nb < - > na - - > b
		if nb_ne ~= nil then
            nb_ne.__up_node__ = na				--  A < - > nb < - > na - - > b
		end
    elseif na_up == nb then--相邻   A < - > nb < - > na < - > B
        na.__up_node__      = nb_up		--  A < - - na - - - nb - - - b
		nb_up.__next_node__ = na  		--  A < - > na - - - nb - - - b
        na.__next_node__    = nb			--  A < - > na - - > nb - - - b
		nb.__up_node__      = na			--  A < - > na < - > nb - - - b
		nb.__next_node__	   = na_ne      --  A < - > na < - > nb - - > b
		if na_ne then
			na_ne.__up_node__   = nb			--  A < - > na < - > nb < - > b
        end
    else
        na_up.__next_node__ = nb 			--  A - - > nb - - - B - - - na - - - C
        nb.__up_node__ = na_up				--  A < - > nb - - - B - - - na - - - C
        nb.__next_node__ = na_ne 			--  A < - > nb - - > B - - - na - - - C
        if na_ne then
            na_ne.__up_node__ = nb   		--  A < - > nb < - > B - - - na - - - C
        end
        nb_up.__next_node__ = na 			--  A < - > nb < - > B - - > na - - - C
        na.__up_node__ = nb_up   			--  A < - > nb < - > B < - > na - - - C
        na.__next_node__ = nb_ne 			-- 	A < - > nb < - > B < - > na - - > C
        if nb_ne then
            nb_ne.__up_node__ = na   	    -- 	A < - > nb < - > B < - > na < - > C
        end
    end
    if na.__next_node__ == nil then
        self.__tail_node = na
    end
    if nb.__next_node__ == nil then
        self.__tail_node = nb
    end


    return self
end

local function find_node(head,func)
    local node = head
    while node do
        if func(node) then
            return node
        end
        node = node.__next_node__
    end
end

local function ins_node(self,node)
    if self:is_empty() then
        list_insert_node_back(self,node)
    else
        local head = 
        self:get_interval_head(self:get_interval_idx(node.depth))
        or self.__root_node.__next_node__

        self:set_as_interval(node)

        local find_node = find_node(head,function(fnode)
            return fnode.depth >= node.depth 
        end)

        if find_node == nil then
            list_insert_node_back(self,node)
        else
            list_insert_self_up(self,find_node,node)
        end
    end
    return node
end

function depth_list:__init__(interval)
    self._interval_size = interval or 200
end

function depth_list:get_interval_idx(depth)
    return math.floor(depth / self._interval_size)
end

function depth_list:get_interval_head(i)
    return self.__interval[i]
end

function depth_list:set_as_interval(node)
    local depth = node.depth
    local idx = self:get_interval_idx(depth)
    local inte_head = self:get_interval_head(idx)
    if inte_head then
        if inte_head.depth > depth then
            self.__interval[idx] = node
        end
    else
        self.__interval[idx] = node
    end
end

function depth_list:__init__()
    self.__tail_node = self.__root_node
end

function depth_list:is_empty()
    return self.__root_node.__next_node__ == nil
end

function depth_list:get_tail()
    return self.__tail_node
end

function depth_list:clear()
    self.__root_node.__next_node__ = nil
    self.__tail_node = self.__root_node
    self.__all_node = {}
    self.__node_number = 0
    self.__node_index = {}
end

function depth_list:get_node(index)
    if index <= 0 or index > self.node_number then
        return
    end
    local node = self.__root_node
    for i = 1, index do
        node = node.__next_node__
    end
    return node
end

function depth_list:find(condition)
    if condition == nil then return end
    for node in self:items() do
        if condition(node) then
            return node
        end
    end
    return nil
end

function depth_list:_update_node_depth(node)
    local depth = math.ceil(node.depth)
    local up_depth = node.__up_depth__ or math.huge
    if depth ~= up_depth then
        node.__up_depth__ = depth
        self:set_as_interval(node)
        if depth > up_depth then
            local i_node = node.__next_node__
            while i_node ~= nil do
                if i_node.depth < depth then
                    list_nswap(self,i_node,node)
                end
                i_node = i_node.__next_node__
            end
        elseif depth < up_depth then
            local i_node = node.__up_node__
            while i_node ~= nil and (not i_node.___is_root___) do
                if i_node.depth > depth then
                    list_nswap(self,i_node,node)
                end
                i_node = i_node.__up_node__
            end
        end
    end
    node.__up_depth__ = depth
end

function depth_list:insert(data,depth)
    if not data then return end
    depth = depth or 0
    local node = {data = data,depth = depth}
    return ins_node(self,node)
end

function depth_list:insert_node(node,depth)
    if not node then return end
    node.depth = depth or node.depth or 0
    return ins_node(self,node)
end


function depth_list:index_insert(index,data,depth)
    if self.__node_index[index] == nil then
        local node = self:insert(data,depth)
        self.__node_index[index] = node
    end
end

function depth_list:index_remove(index)
    local node = self.__node_index[index]
    if node then
        self.__node_index[index] = nil
        self:remove_self(node)
    end
end

function depth_list:remove_self(node)--节点自删除
    if not node then return end
    local up = node.__up_node__
    local next = node.__next_node__

    if next == nil then
        self:remove_back()
    else
        up.__next_node__ = next
        next.__up_node__ = up
        if up.__next_node__ == nil then
            self.__tail_node = up
        end
    end
    self.__all_node[node] = nil
end

function depth_list:remove_back()
    local node = self.__tail_node
    local tail = node.__up_node__
    node.__up_node__.__next_node__ = nil
    self.__all_node[node] = nil
    self.__tail_node = tail
    return node
end

function depth_list:remove(index)
    local node = self:get_node(index)
    if node then
        local up = node.__up_node__
        local next = node.__next_node__

        up.__next_node__ = next
        if next then
            next.__up_node__ = up
        end

        self.__all_node[node] = nil
        if up.__next_node__ == nil then
            self.__tail_node = up
        end

        self.node_num = self.node_num - 1
        return node
    end
end

function depth_list:items()
    local node = self.__root_node

    return function()
        node = node.__next_node__
        return node
    end
end

function depth_list:eitems()
    local node = self.__tail_node

    return function()
        if node.___is_root___ then
			return nil
		end
		local n = node
        node = node.__up_node__
        return n
    end
end

return depth_list